package com.lie.prepare.algorithm.sort;

import java.util.Arrays;

import static com.lie.prepare.util.Print.*;
/**
 * Created by lie on 2018/4/13.
 * 归并排序 稳定的排序算法
 *
 * 时间复杂度是 n*log(n)
 * 看起来吊打其他算法，但是是以空间换时间的——里面一直在创建temp[]
 */
public class MergeSort {

    //想象一下二叉树
    //把数组一直分割，直到最下面的一组只有[1,2][1]这样的一到2个数据
    public static int[] doSort(int[] array, int left, int right){
        int mid = (right+ left)/2;
//        print("left="+left+" right="+right+" mid="+mid);
        if (left < right) {
            doSort(array, left, mid);
            doSort(array, mid+1, right);

            merge(array, left, mid, right);
        }

        return array;
    }

    //开始合并
    //由于迭代，可以保证更细粒度的数组源的数据都是有序序列
    //所以这里是合并2个有序序列
    private static void merge(int[] array, int left, int mid, int right){

        int indexLeft = left;
        int indexRight = mid + 1;

        int indexTemp = 0;//供缓存数组用的
        int[] temp = new int[right - left +1];

        while (indexLeft <= mid && indexRight <= right) {
            //temp存2个有序序列中，比较小的元素
            if (array[indexLeft] < array[indexRight]) {
                temp[indexTemp ++] = array[indexLeft++];
            }else {
                temp[indexTemp ++] = array[indexRight++];
            }
        }

        //再把原来2个序列剩下的元素，放入temp中，以下2个操作只会执行其中某一个
        while (indexLeft <= mid) {
            temp[indexTemp ++] = array[indexLeft++];
        }
        while (indexRight <= right) {
            temp[indexTemp++] = array[indexRight++];
        }

        //这时候已经得到一个合并了2个有序序列的temp数组
        //是时候把temp的数据覆盖原来array从left到right这段范围里的数据了
        for (int i = 0; i < temp.length; i++) {
            array[left++] = temp[i];
        }

        print("合并， "+ Arrays.toString(temp));

    }


    public static void main(String[] args){
        int[] array = {-1, 1, 4, 99, 0, 2, 5, 7};
//        merge(array, 0, 4, 7);

        int[] afterSort = doSort(array, 0, array.length-1);
        print("事后， "+ Arrays.toString(afterSort));

    }
}
